package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.entity.TreeNode;

/**
 * @author qezhhnjy
 * @date 2020/12/9-23:02
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 */
public class ArrayToBinarySearchTree {

    public static TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private static TreeNode dfs(int[] nums, int low, int high) {
        if (low > high) return null;

        int mid = low + (high - low)/2;
        TreeNode node = new TreeNode(nums[mid]);

        node.left = dfs(nums, low, mid - 1);
        node.right = dfs(nums, mid + 1, high);

        return node;
    }
}
